This tag is for basic 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)

2
votes
2answers
42 views

A man, woman, boy, girl, cat, and dog are walking down a path..

I'm hoping someone can explain how this works. The problem: A man, woman, boy, girl, cat, and dog are walking down a path in single file. How many ways can this happen if the dog is between the man ...
2
votes
0answers
24 views

Existence of a Transversal in a Cycle

Let a transversal be defined as an independent set of $G$, containing precisely one vertex from each $V_i$. Let $G = (V,E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup \ldots \cup V_n$ be ...
6
votes
2answers
96 views

Combinatorial proof of $\sum_{k=0}^n k \cdot k! = (n+1)! -1$

Is there a nice combinatorial proof of the following identity? (That is, by showing that both sides count the same thing.) $$\sum_{k=0}^n k \cdot k! = (n+1)! -1 $$ I was searching Wikipedia for nice ...
0
votes
1answer
36 views

An n-bit boolean function maps 0/1 strings to 0 or 1

$f: \{0,1\}^n -> \{0,1\}$ The function "depends on i" if there exists two $o/1$ strings (A and B) where A and B differ only at position i and $f(A) \not= f(B)$. How many n-bit Boolean functions ...
1
vote
1answer
72 views

Does anyone know what this notation means: $n^{\underline{n}}$?

This is what I don't understand: $n^{\underline{n}}$ This is in a Combinatorics paper I am working my way through, and n is some natural number. I think that it should mean $n!$ The full question is ...
0
votes
0answers
17 views

The summation of product of factorials

So the question is $\sum\limits_{x=0}^n \frac{(\beta+n-x)! (\alpha+x)!}{x!(n-x)!}$. I got the following result from mathematica yet I don't know how to prove it. Can anyone give me some help?
1
vote
2answers
80 views

Binomial Expansion.

So I had a question: Prove that for $n \geq 1$, $${n \choose 1} + 2{n \choose 2} + 3{n \choose 3} + ...+ n{n \choose n} = n2^{n-1}$$ So my idea was to take the binomial expansion of $(1+1)^n$ which ...
1
vote
2answers
51 views

Algebraic proof for the following identity

Give an algebraic proof that $\binom{n+1}{m+1} = \sum_{k=m}^{n} \binom{k}{m}$. I've tried using Pascal's rule and looking for a telescopic sum, but I can't find one. Any help is appreciated.
0
votes
0answers
19 views

Ordering elements from multiple sets without breaking groups

Let's say I have N (unordered) sets which may be intersecting, with a total of K elements (in the union of all sets). How do I choose K elements so that the elements from the same sets form contigous ...
2
votes
2answers
27 views

Ordinary Generating functions for $b_n$

Problem Let $f(x)$ be a ordinary generating function for the sequence $ \{\ a_0, a_1, a_2... \}\ $ Find the ordinary generating function for $b_0 = b_1 = 0, b_2 = 1$ $b_n = a_n$ for $n \geq 3$. Also ...
0
votes
1answer
51 views

Prove it is possible to pick 11 integers whose sum is divisible by 11 [closed]

I'm not sure how to write a formal proof for this problem. I can come up with multiple examples, but I need to prove formally that there exists a subset of 11 integers whose sum is divisible by 11. ...
2
votes
1answer
26 views

Some help with generating functions

Problem Let $f(x)$ be the ordinary generating function for the sequence $ \{\ a_0 , a_1, a_2,... \}\ $. Find the ordinary generating sequence for the following sequence: $$b_n = a_n + c \ \ \ , n \in ...
0
votes
1answer
28 views

Counting Balls / Elementary Generating Functions

I have a quiz tomorrow in an elementary combinatorics class, and I'm trying to understanding these generating function problems. For some reason, I can't see to figure out how to set these two up. ...
0
votes
0answers
27 views

i need someone to formulate this combinatorics for me

I have \$7, \$6, \$5, \$4, \$3, \$2, \$1 My question is: by combining any 3 of this, how many times will i get \$12. I know how to do this by iterating using lexicographic ordering but i want a ...
1
vote
3answers
31 views

Probability that the second ball is red

n balls, each equally likely to be red or black, are added to a box containing one red ball. Given that the first ball withdrawn from the box is red, what's the probability that the second ball ...
12
votes
0answers
113 views

Involutions, RSK and Young Tableaux

Let $S_n$ be the symmetric group on $n$ elements. The Robinson-Schensted-Knuth (RSK) correspondence sends a permutation $\pi\in S_n$ to a pair of Standard Young Tableaux $(P,Q)$ with equal shapes ...
0
votes
1answer
62 views

What class am I most prepared for?

I've only taken up to calc 3, discrete, and linear algebra. Which course am I most prepared for? I'm going to be taking differential equations and advanced calc, but I want to take a 3rd class. I can ...
0
votes
1answer
40 views

Count how many arrays of a specific type exist - O(N) Dynamic Programming

Consider an array of N + 2 binary digits (1 and 0), which contains at least one '1' and three '0'. The last and first digit of the array is 0. Given two numbers, let's say p and q, determine how many ...
1
vote
1answer
28 views

minimum number of repetitions in a string

I have a string of length $n$ from an alphabet $A$ with $s$ symbols. What is the probability of having at least $k$ equal characters? It does not seem a binomial, nor a $1-$... form, nor a bar and ...
0
votes
0answers
24 views

Number of permutations with double restriction

Task is as follows: Let's have 6 element set, there are obviously $6!$ permutations of this set, but there are two restrictions: element 1 and 2 have to be in one cycle and element 3 can't be with 1 ...
0
votes
2answers
26 views

How many good words are there?

A “good” word is any seven letter word consisting of letters from $\{A,B,C\}$ (some letters may be absent and some letter can be present more than once), with the restriction that $A$ cannot be ...
3
votes
1answer
39 views

Simple combinatorics question, sanity check.

Sorry if I'm wasting everyone's time. I'm checking a homework set, and I'm a little confused by the solution manual's answers, and want a second opinion before shrugging it off as a mistake. Consider ...
0
votes
0answers
21 views

A coin is tossed m+n times.(m>n) How many outcomes have at least m consecutive heads?

The problem I face is(obviously for which the question was intended) that, suppose $m=3$,$n=2$, then ${HHH,H,T}$ and ${H,HHH,T}$ are same while ${HHH,T,H}$ and ${H,T,HHH}$ are different. Hence, I ...
0
votes
1answer
13 views

multi-index number of index

I was wondering how can I get the number of index in a multi-index notation? if $\alpha \in \mathbb{N_0^n}$ is multi-index such that $ | \alpha|= \sum_{i=1}^{n} \alpha_i$ How many index do I have if ...
1
vote
2answers
51 views

Understanding the partition function

I have been trying, as a toy problem, to implement in either the Python or Haskell programming languages functions to calculate the partitions for a number and the count of those partitions. I have no ...
0
votes
3answers
35 views

Number of ways to form committee

A committee of 6 is being formed from a group of 12 sophomores and 10 freshmen. How many committees can be formed if at least 3 have to be sophomores? I know one way is to split this into cases ...
2
votes
0answers
27 views

Maximum number of tile possible in 2048 game? [duplicate]

Ok my question is what is the maximum number of tile we can make in the 2048 game assuming we were really lucky and got all 4 number tiles and got the new squares exactly where we needed them?
0
votes
2answers
36 views

Ordinary generating functions problem

Problem Find the ordinary generating function for each of the following sequences. In each case the sequence is defined for all $n \in \mathbb{N}_0$. $$a_n = n$$ I'm having a very hard time ...
1
vote
0answers
51 views

Pancake and increasing order

Determine the number of 5 pancake stacks that requires exactly 2 flips to put into the increasing order, i.e., 1,2,3,4,5. (Example: 3,4,2,1,5 is one of them.)
1
vote
1answer
18 views

On the number of midpoint free subsets

A set $X$ of real numbers is called midpoint free if whenever $x,y$ are distinct elements of $X$ then $\frac{x+y}2 \not \in X$. What is number of midpoint free subsets of $\{1,2,...,n\}$?
-3
votes
1answer
53 views

Number of ways of choosing three fruits [closed]

You are allowed to choose three fruits from a tray containing two identical apples, two identical oranges, a pear, a banana, and a plum. In how many ways can you choose?
0
votes
2answers
46 views

how many integers are there between 10 000 and 99 999…

how many integers are there between 10 000 and 99 999 a) whose digits are are each odd? b) with no repeated digits? c) with no repeated digits and whose digits are each odd? I know there are 90 ...
2
votes
1answer
56 views

Compositions - Fruit Salad

I'm asked to find $s(n)$ which is the number of ways to make a fruit salad with $n$ pieces of fruit, given that we must use strawberries by the half-dozen, an odd number of apples, between 2 and 7 ...
1
vote
2answers
41 views

I need to proove this, but I'm lost.

Prove for all integers $n \geq 1$ ${n\choose 0} - \frac12 {n \choose 1} + \frac{1}{2^2} {n \choose 2} - \frac{1}{2^3} {n\choose 3} + \cdots + (-1)^{n-1}\frac{1}{2^{n-1}} {n \choose n-1} = \left\{ ...
0
votes
1answer
37 views

notation of all possible combinations

Suppose we have list of Q integers $p_1, p_2,..., p_Q$. In round $k$ we have combinations of the integers. For example Q = 3, the combinations of $k$ round are: k= 1, $p_1, p_2,p_3$ . k= 2, ...
0
votes
1answer
57 views

Finding Number of Edges and Vertices in Icosahedron

This is a practice question from a practice test I am working on. ...
1
vote
1answer
30 views

Binomial Coefficient Recusions

Let m and j be non-negative integers. Define $S^{0}_{m} = 1$ and: $ S^{j}_{m} = \displaystyle\sum\limits_{i=1}^{m} S_{i}^{j-1}$ Show via induction: $ S_{m}^{j} = {m+j-1 \choose j} $ I can ...
0
votes
2answers
45 views

Obtaining a linear recurrence from differential equation

I need some guidance with the following problem. I have a sequence $L_0,L_1,\ldots$ whose ordinary generating series satisfies $$L(x) = \sum_{n=0}^{\infty} L_n \frac{x^n}{n!} = \frac{1}{2-e^x}.$$ ...
1
vote
0answers
16 views

Non-Intersecting up-right lattice paths and standard Young Tableaux

Consider the Lattice $\mathbb{Z}^2$ and an initial set of points with coordinates $(0,u_1)$, $(0,u_2)$, $\cdots$ $(0,u_n)$, final set of points $(m,v_1),(m,v_2),\cdots,(m,v_n)$, where $v_i,u_i$ are ...
1
vote
1answer
66 views

You bought six numbers at your local hardware store. The numbers are 0, 1, 2, 3, 4, 5.

I got this question and can't crack it. Any help will be appreciated. You bought six numbers at your local hardware store. The numbers are 0, 1, 2, 3, 4, 5. a) How many 6 digit house numbers would ...
1
vote
1answer
44 views

Combinatorics with balls and bins with constraint

I have $90$ identical balls to distribute among $64$ distinguishable bins. Each must get at least 1 ball, after that the distribution over the remaining $26$ does not matter. I know I first have to ...
-1
votes
0answers
13 views

Combinatorial Designs 1-Factorizations

Construct a starter of order 5 (on Z12) and from it construct a 1-factorization for K14.
1
vote
0answers
24 views

Chu-Vandermonde-like combinatorial identity

I am looking for a simple combinatorial proof of the binomial identity: $$\sum_{j=0}^n \binom{2j}{j}\binom{2n-2j}{n-j} = 4^n.\tag{1}$$ The standard way I know is to exploit the generating function: ...
1
vote
1answer
59 views

Combinatorial Proof of Identity

How do I build a combinatorial proof of the following recursion: $$\binom {n}{k} = (k+1)\binom {n-1}{k}+(n-k)\binom {n-1}{k-1}$$ I'm having really big difficulties in finding the right way to ...
3
votes
1answer
43 views

Number of subsets without consecutive numbers

Consider $S=\{1,2,\ldots,15\}$. Let $X$ denote the number of subsets of $S$ of four elements which contain no consecutive numbers. The claim is that $X$ equals the coefficient of $x^{14}$ in ...
1
vote
1answer
40 views

Prove combinatorial identity

Prove the following identity: $$ {{i+j}\choose{i}}\left\{{n}\atop{i+j}\right\} = \sum_{k=0}^n{{n}\choose{k}}\left\{{k}\atop{i}\right\}\left\{{n-k}\atop{j}\right\} $$
2
votes
1answer
31 views

Counting problem involving Hat Check experiment with n hats

The question is a spin on the Hat Check problem. "There are n= 2k hats (an even number). Find the probability of B = { $h_{i} = i$ if $i$ is even and $h_{i} \neq i$ if $i$ is odd)." My interpretation ...
0
votes
2answers
42 views

Matching 5 couples in a tennis tournament

Let's say there are 5 men (Arthur, Bob, Charlie, David and Earl) and there are 5 women (Francine, Grace, Heather, Isabella and Jessie), who want to participate in a mixed-doubles tennis tournament. ...
4
votes
2answers
58 views

What is the number of compositions of the integer n such that no part is unique?

I want to find the generating function for the number of compositions (ordered partitions) of n such that no part is unique ( equivalently, every part appears at least twice). For example: there are ...
1
vote
1answer
44 views

Finding the coefficient of a generating function

Given $f(x) = x^4\left(\frac{1-x^6}{1-x}\right)^4 = (x+x^2+x^3+x^4+x^5+x^6)^4$. This is the generating function $f(x)$ of $a_n$, which is the number of ways to get $n$ as the sum of the upper faces of ...