For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

0
votes
1answer
35 views

Some men and women are randomly assigned seats at a round table and no two persons of the same sex are seated next to each other. Probability of this?

Four women and four men are assigned seats at random at a round table. what is the probability that no two persons of the same sex will be sitting next to each other?
0
votes
0answers
45 views

how would i simplify this into an identity?

$$ B_{n,k}^{f\ln(g)} = B_{n,k}\left(\frac{d}{dx}[f(x)\ln(g(x))], \frac{d^2}{dx^2}[f(x) \ln(g(x)), \cdots, \frac{d^{n-k+1}}{dx^{n-k+1}}[f(x) \ln(g(x))]\right) $$ We know that: $$ B_{n,k}^{f\ln(g)} = ...
0
votes
0answers
19 views

How to find the number of words of length $h$ in a subsets $A$?

Let $L=\{0,1\}^*$ (the set of binary words on $0$ and $1$), Given a tuple of words $(w_1,w_2,\cdots,w_n)\in L^n$ and a function $\sigma:[1,n]\to [1,n]$ define the following set: ...
0
votes
2answers
24 views

Permutations; group of 5 boys, 10 girls. What's the probability the person the 4th position is a boy?

Problem description: A group of 5 boys and 10 girls is lined up in random order -- that is, each of the 15! permutations is assumed to be equally likely. What is the probability that the person in ...
1
vote
0answers
46 views

Counting problem of combinations of symmetric matrix.

Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below- $G$ is partitioned in to two sub ...
1
vote
1answer
48 views

Binomial Coefficients and Function Composition

I found a paper that stated the following without proof. I tried to prove it on my own, but so far to no avail. Define $\varphi^{+}: \mathbb{N}^2 \to \mathbb{N}$ by $\varphi^{+}(i,j) = i + j$. ...
3
votes
5answers
179 views

Curious Binomial Coefficient Identity

Consider the following set of identities: ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ... This set ...
1
vote
2answers
43 views

Consider all the permutations of the word “ENDEANOEL”

Consider all the permutations of the word "ENDEANOEL" : 1)What is the number of permutations containing the word "ENDEA" ? I can't understand how to approach this problem!! 2)Number of permutations ...
0
votes
1answer
20 views

Reverse permutation, number of inversions, descents, major index

If $w=a_1a_2...a_n \in S_n $, then let $w^r=a_n....a_2a_1$, the reverse of $w$. Express inv($w^r$), des($w^r$) and maj($w^r$) in terms inv($w$), des($w$), maj($w$), respectively. It from Stanley's ...
4
votes
1answer
121 views

Complex Analysis proof of multinomial expression

I've recently come across the following identity $$ \displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n} $$ A nice complex analysis proof (by Felix Marin, here) follows as: ...
2
votes
1answer
28 views

How do people find the number of ways you can put together a rubiks cube?

Just curious. How do people actually find the number of ways you can put together a rubiks cube? How do you find the number of choices? Do you use the same permutation formula? Insight would be ...
3
votes
3answers
107 views

Is this permutations or combinations?

I am a bit confused. When we use the multiplicative principle are we finding the number of permutations or combinations. An example of using this principle is where I have $5$ shirts $3$ pairs of ...
0
votes
1answer
36 views

Combination formula?

I know there is a formula for finding the different combinations when you are dividing them in groups: $$\binom{n}{r} = \frac{n!}{(n-r)!\, r!}$$ However, what if you just want to find the number of ...
1
vote
2answers
3k views

number of ordered partitions of integer

Please, help me out How to evaluate the number of ordered partitions of the positive integer 5 Thanks!
0
votes
0answers
21 views

Other than the icosahedron in which each vertex has degree 5, is there any triangulation of the sphere that meets the following three conditions?

Every vertex has degree > 3. There is no separating triangle (a triangle with vertices of the graph both inside and outside the triangle). Every vertex-coloring using exactly four colors consists of ...
2
votes
1answer
104 views

Probability of selecting the winning numbers in a lottery

I've been studying combinatorics for a while. I've solved a problem but I'm not sure if I'm right. I'll just copy-paste the problem here. In a lottery, six distinct numbers are selected at random ...
-1
votes
2answers
24 views

How many ways are there to arrange three of the letters chosen from the set ABCDE? [closed]

Please show your work. I've been looking at this problem for over an hour now and havn't been able to solve it. Thank you!
0
votes
1answer
34 views

Why do (the ranges of) these sequences intersect?

Let $\{(a_n,b_n)\}$, ($1\le n\le N$) be a finite sequence and $\{(s_n,t_n)\}$ ($n\ge 1$) be an infinite sequence, both in $(\{0\}\cup \mathbb{Z}^{+})^2$. We have $a_1=0$ and $b_N=0$. Also, either ...
0
votes
1answer
42 views

Number of paths in a graph with infinite nodes

Does a graph with infinite nodes that is not fully connected have a countably infinite or a uncountably infinite number of paths originating from a single node? We are only concerned with paths that ...
-4
votes
1answer
31 views

Combinatorics Generating Functions [closed]

Any tips/comments would be greatly appreciated! Compute the generating function of the number sequence $h_n = (-2)^n n^2$ where $n\geq 0$.
0
votes
4answers
66 views

Combinatorial Proof of an Instance of the Binomial Theorem

Give a combinatorial proof of the following instance of the binomial theorem. For any positive integer $k$, $(k + 1)^{n}$ = $\sum\limits_{i=0}^{n}$ ${n}\choose{i}$$k^{i}$. I have looked at this for ...
2
votes
0answers
45 views

Coupon collector variation (with deleterious coupons and tolerance)

Imagine the standard coupon collector's problem, with n coupons to be collected. However, the sample space also contains T bad coupons. Specifically, if during the collection, I collect more than t (t ...
0
votes
1answer
41 views

Generating function of derangements

I am pretty new to the topic of generating functions and I would appreciate if someone could help me out with this problem I have. In the lecture we have proven the following generating function for ...
0
votes
2answers
20 views

Prove that if $k\mid n$ then $p(A_k)={1\over k}$

Let $n$ be a natural number, $n=p_1^{a_1}\cdot...\cdotp_m^{a_m}$. Let us randomly choose a number between 1 and $n$ with a uniform, equal chance. Let us denote the event "The number chosen is ...
-5
votes
1answer
34 views

Need help in solving [closed]

A group of $60$ children attend an after school club. Of these, $35$ children play football and $29$ play hockey. Three children do not play either football or hockey. Find the number of children ...
1
vote
1answer
48 views

How many solutions of equation

How many solutions of equation $x_1+x_2+x_3+x_4=n$ in $N_0$ such that $x_1\leq x_2\leq x_3 \leq x_4$? I found solutions of $x_1+x_2+x_3=n$ in $N_0$ , $x_1\leq x_2\leq x_3 $ in the following way : ...
1
vote
1answer
28 views

Difference : subsequences and substrings [closed]

What are the differences between subsequences and substrings?
0
votes
1answer
68 views

Proving $\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$

Prove the identity: $\displaystyle\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$ It looks a bit similar to the "no gets their own hat back" problem or inclusion exclusion ...
1
vote
1answer
48 views

What is the probability that you get $i$ on the $i^{th}$ trial?

What is the probability that you get $i$ on the $i^{th}$ trial? Match = Get result $i$ on $i^{th}$ trial. What is the probability of $M = 0,1,2,...,6$ matches when: Note: I'm not asking you to do ...
5
votes
3answers
103 views

Find the coefficient of $x^{30}$.

Find the coefficient of $x^{30}$ in the given polynomial $$ \left(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}+x^{12}\right)^5 $$ I don't know how to solve problems with such high degree.
1
vote
2answers
694 views

How many ways I can place some, possibly all, five distinct balls into three distinguishable bins?

I want to know how many ways I can place some, possibly all of five balls each a distinct color into three distinguishable bins. Each bin must have at least one ball and I do not need to use all of ...
1
vote
2answers
43 views

Combinatorics Recurrence relation

Let $h_n$ be a number sequence where $h_n = 3h_{n-1} - 2h_{n-2}$ with $h_0 = 0$ and $h_1 = 1$. Compute the ordinary generating function of $h_n$ and then using the generating function compute a ...
2
votes
2answers
23 views

Probability of Two Suits within Three cards, within 4 cards

I am trying to calculate what is the probability of the 3 random cards of 52-pack containing at least two of the same suit. I am also trying to do the same for the four card variant (so, the ...
2
votes
1answer
26 views

Number of ways to select AT LEAST one item from 12 different items. The items are divided into two sets, each of size 6

The answer says 4095. Now, as per my understanding : $4095 = 2^{12} - 1$ == Ways of getting a non-null subset out of 12 elems That would make sense, but where does the "divided into two sets, each ...
3
votes
2answers
61 views

How many sequences of length 6 are formed from the 26 letters without repetition where the first or last letter (possibly both) must not be vowels?

How many sequences of length 6 are formed from the 26 letters without repetition where the first or last letter (possibly both) must not be vowels? I am so lost and confused, but here's my approach: ...
0
votes
1answer
20 views

All subsets of nonnegative integers such that $a+2b = n$ has one solution for every positive integer n

My friend tackled this problem awhile ago and gave it to me recently. To reiterate, I am trying to find all subsets $S$ of the nonnegative integers such that the equation $a+2b = n$, where $a$ and $b$ ...
-1
votes
0answers
28 views

Combinatorics: Password consisting of 13 characters. Must contain at least one odd digit, and at most two even digits. How many passwords?

I'm really trying here. I just need help where to go next. Each character is one of the 10 digits 0, 1, 2, ... , 9 What I have so far is that there are 10^13 possible passwords. I'd have to subtract ...
1
vote
0answers
31 views

Proving Crapo's Lemma

Let $L$ be a finite lattice with least and greatest elements $0, 1$, respectively, and let $X\subseteq L$. Let $n_k$ be the number of $k$-element subsets of $X$ with join $1$ and meet $0$. I want to ...
-1
votes
0answers
19 views

Combinatorics Question for generating fuctions [closed]

Any tips/helps would be greatly appreciated! Let h_n be a number sequence where h_n = 3h_(n-1) - 2h_(n-2) with h_0 = 0 and h_1 = 1. Compute the ordinary generating function of h_n, and then compute a ...
0
votes
1answer
18 views

Sets of non-complements elements in a lattice.

Let $L$ be a finite lattice with a least element $0$ and a greatest element $1$, where $0\neq 1$. Fix a $t\in L$, and let $X$ be the set of non-complements of $t$, i.e., the set of all $x$ such that ...
0
votes
0answers
10 views

Finding a permutation class that has a growth rate greater than 1 and less than 0?

In a permutation class, there is an upper growth rate such that $gr(C)=\limsup_{n\rightarrow \infty}=\sqrt[n]{|C_n|}$ and a lower growth rate such that $\liminf_{n\rightarrow \infty}=\sqrt[n]{|C_n|}$. ...
2
votes
0answers
26 views

Find number of $r$-element subset of $S$ satisfying a property

Let $S= \{1,2,...,1990\}$. A $31$-element subset $A$ of $S$ is said to be good if the sum of all the elements of $A$ is divisible by $5$. Find the number of $31$-element subsets of $S$ which are good. ...
2
votes
1answer
54 views

Combinatorics Question VS CS solution!

I was wondering for some conceptual understanding to a question of this form: In how many ways may we choose three distinct integers from [1, 2, ..., 80] so that one of them is the average of the ...
1
vote
3answers
54 views

Prove that $x^2 - 2013^2 \le y \le 2013^2 - x^2$ has an odd number of solutions

$x$ and $y$ are integers. $N$ is the number of solutions $(x, y)$ of this inequation $x^2 - 2013^2 \le y \le 2013^2 - x^2$. Prove that N is odd.
2
votes
1answer
58 views

Number of orbits of $G$ acting on $X$

This question comes from Algebraic Combinatorics: Walks , Trees, Tableaux, and More by Richard P. Stanley. It is written as follows: "Let $X$ be a finite set, and let $G$ be a subgroup of the ...
2
votes
6answers
5k views

If there are 50 notes whose total value is 100 rupees but 2 rupee note should not be there in the count of those50 notes How many such notes can be?

If there are 50 notes whose total value is 100 rupees but 2 rupee note should not be there in the count of those 50 notes.How many such notes can be ? Notes available are $1$ Rupee $2$ Rupees ( but ...
0
votes
0answers
16 views

Mobius function on posets

Let $A= \lbrace 1^{a_1},2^{a_2},...,n^{a_n} \rbrace $ and $B=\lbrace 1^{b_1},2^{b_2},...,n^{b_n} \rbrace $ multisets for which : $A\leq _P B \Leftrightarrow $ for all $i=1,2,...,n $ is $a_i\leq b_i$. ...
2
votes
0answers
17 views

Optimality of lower bounds for Max-cut on specific graphs

The Max-Cut problem asks to find a subset $S$ of the vertices of a graph (with $m$ edges) such that the number of edges from $S$ to it's complement is as large as possible. The size $|M|$ of a max cut ...
0
votes
3answers
39 views

Product Rule Notation Meaning

Let $S_1,...,S_t$ be finite sets and let $S=S_1 \times ... \times S_t$. The product rule states that $$|S|= _{i=1}^t S_i$$ There is supposed to be some big pi symbol in between the limits which i ...
1
vote
1answer
24 views

Find all possible two-way associations/relations between four numbers

Given four numbers {1,2,3,4}, how to find all possible two-way associations/relations between them? I calculate them manually as in below (50 in total) but I would like to know whether a mathematical ...